package com.lfg.leetcode.leetcode1000;


import java.util.*;

public class No1291sequentialDigits {
    public static void main(String[] args) {
        System.out.println(sequentialDigits(58, 155));
    }

    public static List<Integer> sequentialDigits(int low, int high) {
        Set<Integer> ret = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        Set<Integer> queueSet = new HashSet<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer value = queue.poll();
                if (null == value) {
                    continue;
                }
                if (value >= low && value <= high) {
                    ret.add(value);
                }
                String str = value.toString();
                char last = str.charAt(str.length() - 1);
                int val = Integer.parseInt(Character.toString(last))+1;
                if (val > 9) {
                    continue;
                }
                value = value * 10 + val;
                if (value <= high && !queueSet.contains(value)) {
                    queueSet.add(value);
                    queue.offer(value);
                }
                if(value < low){
                    continue;
                }
                value = Integer.valueOf(value.toString().substring(1));
                if (value <= high && !queueSet.contains(value)) {
                    queueSet.add(value);
                    queue.offer(value);
                }
            }
        }
        List<Integer> list = new ArrayList<>(ret);
        Collections.sort(list);
        return list;
    }
}

